package Hot100.Medium.Backtracking;

import java.util.ArrayList;
import java.util.List;

/**
 * 分割回文串，将字符串s分割成都是回文串的字串。子集型回溯问题
 * 可以先给字符串间都加一个逗号，然后每个字串还是选与不选的两种操作，可参考LC78的dfs方法
 */
public class LC131 {
    public static void main(String[] args) {

    }

    public List<List<String>> partition(String s){
        List<List<String>> ans = new ArrayList<>();
        List<String> path = new ArrayList<>();
        dfs(0, 0, s, ans, path);
        return ans;
    }

    // 考虑i后面的逗号怎么选择
    // start表示当前这段回文字串的开始位置
    private void dfs(int i, int start, String s, List<List<String>> ans, List<String> path){
        if(i == s.length()){
            ans.add(new ArrayList<>(path));
            return;
        }
        // 不分割，不选i以及i+1之间的逗号
        if(i < s.length() - 1){
            dfs(i + 1, start, s, ans, path);
        }
        // 分割，选i以及i+1之间的逗号
        if(isPalindrome(s, start, i)){
            path.add(s.substring(start, i + 1));// 该方法左闭右开，因此是i+1
            dfs(i + 1, i + 1, s, ans, path);
            path.remove(path.size() - 1);
        }
    }

    private boolean isPalindrome(String s, int left, int right){
        while(left < right){
            if(s.charAt(left) != s.charAt(right)){
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}
